Implementing the Counting Sort Algorithm in C++
**Counting Sort** is a non-comparison sorting algorithm. Its core idea is to construct a sorted array by counting the occurrences of elements, making it suitable for scenarios where the range of integers is not large (e.g., student scores, ages). **Basic Idea**: Taking the array `[4, 2, 2, 8, 3, 3, 1]` as an example, the steps are: 1. Determine the maximum value (8) and create a count array `count` to statistics the occurrences of each element (e.g., `count[2] = 2`); 2. Insert elements into the result array in the order of the count array to obtain the sorted result `[1, 2, 2, 3, 3, 4, 8]`. **Implementation Key Points**: In C++ code, first find the maximum value, count the occurrences, construct the result array, and copy it back to the original array. Key steps include initializing the count array, counting occurrences, and filling the result array according to the counts. **Complexity**: Time complexity is O(n + k) (where n is the array length and k is the data range), and space complexity is O(k). **Applicable Scenarios**: Non-negative integers with a small range, requiring efficient sorting; negative numbers can be handled by offset conversion (e.g., adding the minimum value). Counting Sort achieves linear-time sorting through the "counting-construction" logic and is ideal for processing small-range integers.
Read MoreImplementing the Counting Sort Algorithm in Python
Counting sort is an efficient non-comparison sorting algorithm suitable for integers with a small value range. Its time complexity is O(n + k), where n is the number of elements and k is the data range. Core steps: 1. Determine the data range (find min and max); 2. Construct a counting array to count the occurrences of each element; 3. Output the elements of the counting array in order (outputting the number of times corresponding to the count). It is stable (relative order of duplicate elements remains unchanged), and memory usage depends on the data range. It is suitable for integer data with many duplicates or a small range (e.g., exam scores). The Python implementation completes sorting through boundary handling, counting occurrences, etc. Test cases verify its applicability to arrays with duplicate elements and negative numbers.
Read More